package SubjectBacktracking.Two;

import java.util.ArrayList;
import java.util.List;

public class Subsets {

/**
 * 难度：中等
 * 
 * 78. 子集
 * 	给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
 * 	解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
 * 	
 * 示例 1：
 * 	输入：nums = [1,2,3]
 * 	输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
 * 	
 * 示例 2：
 * 	输入：nums = [0]
 * 	输出：[[],[0]]
 * 	
 * 提示：
 * 	1 <= nums.length <= 10
 * 	-10 <= nums[i] <= 10
 * 	nums 中的所有元素 互不相同
 *
 * */
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Subsets s= new Subsets();
		System.out.println(s.subsets(new int[] {1,2,3}));
	}

	List<List<Integer>> result = new ArrayList<>();
	List<Integer> path = new ArrayList<>();
	public List<List<Integer>> subsets(int[] nums) {
		backtracking(nums, 0);
		return result;
    }
	private void backtracking(int[] nums, int startIndex) {
		result.add(new ArrayList<>(path));	// 收集子集
//		if(startIndex==nums.length) {		// 终止条件可以不加
//			return;
//		}
		for(int i=startIndex;i<nums.length;i++) {
			path.add(nums[i]);
			backtracking(nums, i+1);
			path.remove(path.size()-1);
		}
	}
	
	//方法一：迭代法实现子集枚举
	List<Integer> t = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    public List<List<Integer>> subsets1(int[] nums) {
        int n = nums.length;
        for (int mask = 0; mask < (1 << n); ++mask) {
            t.clear();
            for (int i = 0; i < n; ++i) {
                if ((mask & (1 << i)) != 0) {
                    t.add(nums[i]);
                }
            }
            ans.add(new ArrayList<Integer>(t));
        }
        return ans;
    }
    //方法二：递归法实现子集枚举
//    List<Integer> t = new ArrayList<Integer>();
//    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    public List<List<Integer>> subsets2(int[] nums) {
        dfs(0, nums);
        return ans;
    }
    public void dfs(int cur, int[] nums) {
        if (cur == nums.length) {
            ans.add(new ArrayList<Integer>(t));
            return;
        }
        t.add(nums[cur]);
        dfs(cur + 1, nums);
        t.remove(t.size() - 1);
        dfs(cur + 1, nums);
    }
}
